package com.example.leetcode;

/**
 * 动态规划 ** 难点 ** 参考题解
 *  环形子数组的最大和
 *  理解f(i)以i结尾的最大子序
 *  理解sum -最小子序
 */
public class Demo0918 {

    //拼接新数组后子数组问题  超时
    public int maxSubarraySumCircular(int[] nums) {
        int len = nums.length;
        int numsNew[]=new int[2*len-1];
        for (int i = 0; i < len; i++) {
            numsNew[i]=nums[i];
            if (i+len<2*len-1){
                numsNew[i+len]=nums[i];
            }
        }
        int maxVal=numsNew[0];
        for (int j = 0; j < len; j++) {
            int preFun=numsNew[j];
            for (int i = j+1; i <j+len ; i++) {
                preFun=Math.max(preFun+numsNew[i],numsNew[i]);
                maxVal=Math.max(maxVal,preFun);
            }
        }
        return maxVal;
    }

    /**
     * 最大子序和    sum-最小子序和
     * @param nums
     * @return
     */
    public int maxSubarraySumCircular1(int[] nums){
        //1.最大子序和 & 最小子序和
        int preMax=nums[0];
        int maxVal=nums[0];
        int preMin=nums[0];
        int minVal=nums[0];
        int sum=nums[0];
        for (int i = 1; i < nums.length; i++) {
            sum+=nums[i];
            preMax=Math.max(preMax+nums[i],nums[i]);
            maxVal=Math.max(maxVal,preMax);
            preMin=Math.min(preMin+nums[i],nums[i]);
            minVal=Math.min(minVal,preMin);
        }
        if (sum-minVal==0){
            return maxVal;
        }
        return Math.max(maxVal,sum-minVal);
    }
}
